/**
 * 数独核心算法模块
 */

// 数独求解算法（回溯法）
function solveSudokuAlgorithm(board) {
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (board[row][col] === 0) {
                for (let num = 1; num <= 9; num++) {
                    if (isValidMove(board, row, col, num)) {
                        board[row][col] = num;
                        
                        if (solveSudokuAlgorithm(board)) {
                            return true;
                        }
                        
                        board[row][col] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

// 逐步求解数独算法
function solveSudokuStepByStepAlgorithm(board) {
    const steps = [];
    
    function solveWithSteps(b) {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (b[row][col] === 0) {
                    for (let num = 1; num <= 9; num++) {
                        if (isValidMove(b, row, col, num)) {
                            b[row][col] = num;
                            steps.push({ action: 'try', row: row, col: col, num: num });
                            
                            if (solveWithSteps(b)) {
                                return true;
                            }
                            
                            b[row][col] = 0;
                            steps.push({ action: 'backtrack', row: row, col: col, num: num });
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    solveWithSteps(board);
    return steps;
}

// 检查在特定位置放置数字是否有效
function isValidMove(board, row, col, num) {
    // 检查行
    for (let i = 0; i < 9; i++) {
        if (board[row][i] === num) {
            return false;
        }
    }
    
    // 检查列
    for (let i = 0; i < 9; i++) {
        if (board[i][col] === num) {
            return false;
        }
    }
    
    // 检查3x3子网格
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[boxRow + i][boxCol + j] === num) {
                return false;
            }
        }
    }
    
    return true;
}

// 检查数独是否有效
function isValidSudoku(board) {
    // 检查行
    for (let row = 0; row < 9; row++) {
        const seen = new Set();
        for (let col = 0; col < 9; col++) {
            const num = board[row][col];
            if (num !== 0) {
                if (seen.has(num)) {
                    return false;
                }
                seen.add(num);
            }
        }
    }
    
    // 检查列
    for (let col = 0; col < 9; col++) {
        const seen = new Set();
        for (let row = 0; row < 9; row++) {
            const num = board[row][col];
            if (num !== 0) {
                if (seen.has(num)) {
                    return false;
                }
                seen.add(num);
            }
        }
    }
    
    // 检查3x3子网格
    for (let boxRow = 0; boxRow < 3; boxRow++) {
        for (let boxCol = 0; boxCol < 3; boxCol++) {
            const seen = new Set();
            for (let row = boxRow * 3; row < boxRow * 3 + 3; row++) {
                for (let col = boxCol * 3; col < boxCol * 3 + 3; col++) {
                    const num = board[row][col];
                    if (num !== 0) {
                        if (seen.has(num)) {
                            return false;
                        }
                        seen.add(num);
                    }
                }
            }
        }
    }
    
    return true;
}

// 查找数独错误
function findSudokuErrors(board) {
    const errors = [];
    
    // 检查行
    for (let row = 0; row < 9; row++) {
        const seen = {};
        for (let col = 0; col < 9; col++) {
            const num = board[row][col];
            if (num !== 0) {
                if (seen[num]) {
                    errors.push({ row: row, col: col });
                    errors.push({ row: row, col: seen[num] });
                } else {
                    seen[num] = col;
                }
            }
        }
    }
    
    // 检查列
    for (let col = 0; col < 9; col++) {
        const seen = {};
        for (let row = 0; row < 9; row++) {
            const num = board[row][col];
            if (num !== 0) {
                if (seen[num]) {
                    errors.push({ row: row, col: col });
                    errors.push({ row: seen[num], col: col });
                } else {
                    seen[num] = row;
                }
            }
        }
    }
    
    // 检查3x3子网格
    for (let boxRow = 0; boxRow < 3; boxRow++) {
        for (let boxCol = 0; boxCol < 3; boxCol++) {
            const seen = {};
            for (let row = boxRow * 3; row < boxRow * 3 + 3; row++) {
                for (let col = boxCol * 3; col < boxCol * 3 + 3; col++) {
                    const num = board[row][col];
                    if (num !== 0) {
                        const key = `${row},${col}`;
                        if (seen[num]) {
                            errors.push({ row: row, col: col });
                            errors.push({ row: seen[num].row, col: seen[num].col });
                        } else {
                            seen[num] = { row: row, col: col };
                        }
                    }
                }
            }
        }
    }
    
    return errors;
}

// 评估数独难度
function evaluateDifficulty(board) {
    let emptyCells = 0;
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (board[row][col] === 0) {
                emptyCells++;
            }
        }
    }
    
    // 计算已填数字数量
    const filledCells = 81 - emptyCells;
    
    if (emptyCells < 30) return `简单（九宫${filledCells}数）`;
    if (emptyCells < 45) return `中等（九宫${filledCells}数）`;
    if (emptyCells < 60) return `困难（九宫${filledCells}数）`;
    return `极难（九宫${filledCells}数）`;
}

// 生成已解决的数独
function generateSolvedSudoku() {
    // 创建空的9x9棋盘
    const board = Array(9).fill().map(() => Array(9).fill(0));
    
    // 填充对角线的3x3格子（这些格子之间互不影响）
    fillDiagonalBoxes(board);
    
    // 解决剩下的格子
    solveSudokuAlgorithm(board);
    
    return board;
}

// 填充对角线上的3x3格子
function fillDiagonalBoxes(board) {
    for (let i = 0; i < 9; i += 3) {
        fillBox(board, i, i);
    }
}

// 填充一个3x3格子
function fillBox(board, row, col) {
    const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    shuffleArray(numbers); // 随机打乱数组
    
    let idx = 0;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            board[row + i][col + j] = numbers[idx++];
        }
    }
}

// 随机打乱数组
function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

// 从完整解中创建题目
function createPuzzleFromSolution(solution, holes) {
    // 复制完整解
    const puzzle = JSON.parse(JSON.stringify(solution));
    
    // 创建所有可能的位置
    const positions = [];
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            positions.push({ row, col });
        }
    }
    
    // 随机打乱位置
    shuffleArray(positions);
    
    // 挖洞
    let removed = 0;
    for (const pos of positions) {
        if (removed >= holes) break;
        
        const row = pos.row;
        const col = pos.col;
        const backup = puzzle[row][col];
        puzzle[row][col] = 0;
        
        // 检查是否只有一个解
        if (hasOneSolution(puzzle)) {
            removed++;
        } else {
            // 如果不止一个解，恢复数字
            puzzle[row][col] = backup;
        }
    }
    
    return puzzle;
}

// 检查数独是否只有一个解
function hasOneSolution(board) {
    const boardCopy1 = JSON.parse(JSON.stringify(board));
    const boardCopy2 = JSON.parse(JSON.stringify(board));
    
    // 第一次求解
    const solved1 = solveSudokuAlgorithmUnique(boardCopy1);
    
    if (!solved1) return false;
    
    // 尝试用不同的顺序求解，看是否能得到不同的解
    // 通过反转数字尝试顺序
    const solved2 = solveSudokuAlgorithmUnique(boardCopy2, true);
    
    // 比较两个解是否相同
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (boardCopy1[row][col] !== boardCopy2[row][col]) {
                return false; // 有多解
            }
        }
    }
    
    return true; // 只有一个解
}

// 带有唯一解检查的数独求解算法（回溯法）
function solveSudokuAlgorithmUnique(board, reverse = false) {
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (board[row][col] === 0) {
                // 根据reverse参数决定尝试顺序
                const numbers = reverse ? [9, 8, 7, 6, 5, 4, 3, 2, 1] : [1, 2, 3, 4, 5, 6, 7, 8, 9];
                
                for (const num of numbers) {
                    if (isValidMove(board, row, col, num)) {
                        board[row][col] = num;
                        
                        if (solveSudokuAlgorithmUnique(board, reverse)) {
                            return true;
                        }
                        
                        board[row][col] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

// 导出函数
if (typeof module !== 'undefined' && module.exports) {
    module.exports = {
        solveSudokuAlgorithm,
        solveSudokuStepByStepAlgorithm,
        isValidMove,
        isValidSudoku,
        findSudokuErrors,
        evaluateDifficulty,
        generateSolvedSudoku,
        fillDiagonalBoxes,
        fillBox,
        shuffleArray,
        createPuzzleFromSolution,
        hasOneSolution,
        solveSudokuAlgorithmUnique
    };
}